"""
希尔排序
希尔排序可以理解成插入排序的优化版本。希尔排序是先将任意间隔为N的元素有序，刚开始可以是N=n/2，接着让N=N/2，让N一直缩小，当N=1,时，此时序列间隔为1有序。
"""


def shellSortCore(arr):
    gap = len(arr) // 2
    while gap:
        print(gap)
        for i in range(gap, len(arr)):
            m = arr[i]
            for j in range(i - gap, -1,-1):  #j到0
                if m < arr[j]:
                    arr[j], arr[j + gap] = arr[j + gap], arr[j]
        print(arr)
        gap //= 2



if __name__ == "__main__":
    array = [3, 2, 1, 4, 5, 3, 2, 55, 4645, 3, 2, 32, 7, 89, 9, 10]
    shellSortCore(array)
    print(array)
